package h0812;

import java.util.*;
/**
  * @description 高效的任务规划
  * @author 不知名帅哥
  * @date 2024/8/12 14:29
  * @version 1.0
*/
public class EfficientTaskPlanning2 {

    //具体来说，我们应该优先配置那些需要较长时间完成任务的机器，这样可以让这些机器尽早开始执行任务，从而整体完成时间最短。
    //1. 首先对每组任务按照机器执行时间J从大到小排序。执行时间相同的情况下，可以按设置时间B 排序，但这并不是必须的。
    //2. 按照排序后的顺序依次配置每台机器，并记录每台机器的配置完成时间。
    //3. 计算每台机器的任务完成时间（配置完成时间 + 执行时间），并记录最大值作为该组任务的完成时间。
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);

        // 读取任务组数 M
        int M = scanner.nextInt();

        // 保存每组任务的最短完成时间
        int[] results = new int[M];

        // 逐组处理任务
        for (int i = 0; i < M; i++) {
            // 读取机器数量 N
            int N = scanner.nextInt();

            // 用于存储每台机器的设置时间和执行时间
            int[][] bjPairs = new int[N][2];

            for (int j = 0; j < N; j++) {
                bjPairs[j][0] = scanner.nextInt(); // B
                bjPairs[j][1] = scanner.nextInt(); // J
            }

            // 按照执行时间 J 进行排序，降序排列
            Arrays.sort(bjPairs, (a, b) -> b[1] - a[1]);

            int currentTime = 0;
            int maxTime = 0;

            // 依次处理每台机器
            for (int[] bj : bjPairs) {
                int B = bj[0];
                int J = bj[1];

                currentTime += B;
                maxTime = Math.max(maxTime, currentTime + J);
            }

            // 保存当前组任务的最短完成时间
            results[i] = maxTime;
        }

        // 输出所有组任务的最短完成时间
        for (int result : results) {
            System.out.println(result);
        }

        scanner.close();
    }
}
